import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: qian
 * Date: 2022-07-18
 * Time: 11:35
 */
public class Test {
    public static List<String> topKFrequent(String[] words, int k) {
        List<String> list=new ArrayList<>();
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<words.length;i++){
            if(map.containsKey(words[i])){
                int val=map.get(words[i]);
                map.put(words[i],val+1);
            }else{
                map.put(words[i],1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-(o2.getValue());
            }
        });
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if(priorityQueue.size()<k){
                priorityQueue.offer(entry);
            }else{
                if(entry.getValue().compareTo(priorityQueue.peek().getValue())>0){
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }else if(entry.getValue().compareTo(priorityQueue.peek().getValue())==0){
                    String top=priorityQueue.peek().getKey();
                    if(top.compareTo(entry.getKey())>0){
                        priorityQueue.poll();
                        priorityQueue.offer(entry);
                    }
                }
            }
        }
        while (!priorityQueue.isEmpty()){
            list.add(priorityQueue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] words={"i", "love", "leetcode", "i", "love", "coding"};
        int k=2;
        System.out.println(topKFrequent(words, k));
    }
    public static void main3(String[] args){
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        String strSub=sc.nextLine();
        str=str.toUpperCase();
        strSub=strSub.toUpperCase();
        Set<Character> set=new HashSet<>();
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            set.add(ch);
        }
        for(int i=0;i<strSub.length();i++){
            char ch=strSub.charAt(i);
            if(set.contains(ch)){
                set.remove(ch);
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(set.contains(ch)&&(!set.isEmpty())){
                sb.append(ch);
                set.remove(ch);
            }
        }
        System.out.println(sb.toString());
    }
    public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        Map<String,Integer> map=new TreeMap<String,Integer>();
        map.put("hello",12);
        map.put("aaa",1);
        System.out.println(map);
        Set<Map.Entry<String,Integer>> entrySet=map.entrySet();
        for (Map.Entry<String,Integer> entry:entrySet) {
            System.out.println("key:"+entry.getKey()+",value:"+entry.getValue());
        }
    }
    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree=new BinarySearchTree();
        int[] array={3,1,5,2,9,6,4,0,10,23};
        for(int i=0;i<array.length;i++){
            binarySearchTree.insert(array[i]);
        }
       binarySearchTree.remove(10);
        System.out.println("hh");
    }


}
